package com.learning.algorithm.sort.simpleSort;

import com.learning.algorithm.sort.ArraysUtil;
import com.learning.algorithm.sort.CheckSort;
import com.learning.algorithm.sort.IntArraySort;

import java.util.Arrays;

/**
 * @Author: lishi
 * @Description: 插入排序
 * @Date: 2021/11/19 9:34
 */
public class InsertSort implements IntArraySort {
    /**
     * 最简单的插入排序
     *
     * @param arrays
     */
    public static void insertSort(int[] arrays) {
        int loopCounts = 1;
        for (int i = 1; i < arrays.length; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (arrays[j] <= arrays[j + 1]) {
                    break;
                }
                ArraysUtil.swap(arrays, j, j + 1);
            }
            loopCounts++;
        }
    }

    /**
     * 优化插入排序1
     * 使用二分法查找插入位置
     *
     * @param arrays
     */
    public static void insertSort2(int[] arrays) {
        for (int i = 1; i < arrays.length; i++) {
            //            System.out.println("===============第" + i + "次插入start！===============");
            //            System.out.println("排序前 ： " + Arrays.toString(arrays));
            int nowNums = arrays[i];
            int insertPos = findInsertPos(arrays, 0, i - 1, (i - 1) / 2, nowNums);
            if (insertPos >= 0) {
                ArraysUtil.insert(arrays, insertPos, i);
            }
            //            System.out.println("排序后 ： " + Arrays.toString(arrays));
            //            System.out.println("===============第" + i + "次插入end！===============");
        }
    }

    private static int findInsertPos(int[] arrays, int beforePos, int endPos, int nowPos, int insertValue) {
        //        System.out.println(Arrays.toString(arrays));
        //        System.out.println(String.format("beforePos:%s,endPos:%s,nowPos:%s,insertValue:%s", beforePos, endPos, nowPos, insertValue));

        if (insertValue > arrays[endPos]) {
            return -1;
        }

        if (insertValue < arrays[beforePos]) {
            return beforePos;
        }

        if (arrays[nowPos] > insertValue) {
            if (arrays[nowPos - 1] < insertValue) {
                return nowPos;
            }
            return findInsertPos(arrays, beforePos, nowPos, (beforePos + nowPos) / 2, insertValue);
        }

        if (arrays[nowPos] < insertValue) {
            if (arrays[nowPos + 1] > insertValue) {
                return nowPos + 1;
            }
            return findInsertPos(arrays, nowPos, endPos, (nowPos + endPos) / 2, insertValue);
        }
        return nowPos;
    }


    public static void main(String[] args) {
        //        for(int i = 0 ; i < 100; i++) {
        int arrayLength = 1000000;
        int[] originArrays = ArraysUtil.genNoDuplicateIntArray(arrayLength);
        int[] cloneArrays = new int[arrayLength];
        System.arraycopy(originArrays, 0, cloneArrays, 0, arrayLength);
        //        System.out.println("原始数组 ： " + Arrays.toString(cloneArrays));
        long startTime = System.currentTimeMillis();
        insertSort(cloneArrays);
        System.out.println("cost " + (System.currentTimeMillis() - startTime) + " ms");
        //        System.out.println(Arrays.toString(cloneArrays));
        System.out.println(CheckSort.checkSortResult(originArrays, cloneArrays));
        //        }
    }

    public int[] sort(int[] arrays) {
        insertSort(arrays);
        return arrays;
    }

    public String getDesc() {
        return "插入排序";
    }
}
